#ifndef AVL_TREE_H
#define AVL_TREE_H

#include "dsexceptions.h"
#include <algorithm>
#include <iostream> 
#include <queue>
using namespace std;

// AvlTree class
//
// CONSTRUCTION: zero parameter
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x )       --> Insert x
// void remove( x )       --> Remove x (unimplemented)
// bool contains( x )     --> Return true if x is present
// Comparable findMin( )  --> Return smallest item
// Comparable findMax( )  --> Return largest item
// boolean isEmpty( )     --> Return true if empty; else false
// void makeEmpty( )      --> Remove all items
// void printTree( )      --> Print tree in sorted order
// ******************ERRORS********************************
// Throws UnderflowException as warranted

template <typename Comparable>
class AvlTree
{
public:
    AvlTree( ) : root{ nullptr }
	{ }
    
    AvlTree( const AvlTree & rhs ) : root{ nullptr }
	{
	    root = clone( rhs.root );
	}

    AvlTree( AvlTree && rhs ) : root{ rhs.root }
	{
	    rhs.root = nullptr;
	}
    
    ~AvlTree( )
	{
	    makeEmpty( );
	}

    /**
     * Deep copy.
     */
    AvlTree & operator=( const AvlTree & rhs )
	{
	    AvlTree copy = rhs;
	    std::swap( *this, copy );
	    return *this;
	}
        
    /**
     * Move.
     */
    AvlTree & operator=( AvlTree && rhs )
	{
	    std::swap( root, rhs.root );
        
	    return *this;
	}
    
    /**
     * Find the smallest item in the tree.
     * Throw UnderflowException if empty.
     */
    const Comparable & findMin( ) const
	{
	    if( isEmpty( ) )
		throw UnderflowException{ };
	    return findMin( root )->element;
	}

    /**
     * Find the largest item in the tree.
     * Throw UnderflowException if empty.
     */
    const Comparable & findMax( ) const
	{
	    if( isEmpty( ) )
		throw UnderflowException{ };
	    return findMax( root )->element;
	}

    /**
     * Returns true if x is found in the tree.
     */
    bool contains( const Comparable & x ) const
	{
	    return contains( x, root );
	}

    /**
     * Test if the tree is logically empty.
     * Return true if empty, false otherwise.
     */
    bool isEmpty( ) const
	{
	    return root == nullptr;
	}

    /**
     * Print the tree contents in sorted order.
     */
    void printTree( ) const
	{
	    if( isEmpty( ) )
		cout << "Empty tree" << endl;
	    else
		printTree( root );
	}

    /**
     * Make the tree logically empty.
     */
    void makeEmpty( )
	{
	    makeEmpty( root );
	}

    /**
     * Insert x into the tree; duplicates are ignored.
     */
    void insert( const Comparable & x )
	{
	    insert( x, root );
	}
     
    /**
     * Insert x into the tree; duplicates are ignored.
     */
    void insert( Comparable && x )
	{
	    insert( std::move( x ), root );
	}
     
    /**
     * Remove x from the tree. Nothing is done if x is not found.
     */
    void remove( const Comparable & x )
	{
	    remove( x, root );
	}

    /**
     * Print the tree contents in sorted order.
     */
    void displayTree( ) const
	{
	    if( isEmpty( ) )
		cout << "Empty tree" << endl;
	    else
		displayTree( root );
	}

	/**
	 * @brief 打印某一段区间的二叉树上的元素
	 * 
	 * @param k1 
	 * @param k2 
	 */
	void printRange( Comparable k1, Comparable k2)
	{
    	if (k1>k2)
    	{
        	cout << "Mistake: k1>k2" << endl;
        	return;
    	}
    	if (root == nullptr)
    	{
        	cout << "Empty AvlTree."<< endl;
        	return;
    	}
    	printAvl(root,k1,k2);
    	cout << endl;
	}

private:
    struct AvlNode
    {
        Comparable element;
        AvlNode   *left;
        AvlNode   *right;
        int       height;

        AvlNode( const Comparable & ele, AvlNode *lt, AvlNode *rt, int h = 0 )
	    : element{ ele }, left{ lt }, right{ rt }, height{ h } { }
        
        AvlNode( Comparable && ele, AvlNode *lt, AvlNode *rt, int h = 0 )
	    : element{ std::move( ele ) }, left{ lt }, right{ rt }, height{ h } { }
    };

    AvlNode *root;


    /**
     * Internal method to insert into a subtree.
     * x is the item to insert.
     * t is the node that roots the subtree.
     * Set the new root of the subtree.
     */
    void insert( const Comparable & x, AvlNode * & t )
	{
		/// t = nullptr
	    if( t == nullptr )
		t = new AvlNode{ x, nullptr, nullptr };  //实际的插入操作
	    else if( x < t->element )
		insert( x, t->left );
	    else if( t->element < x )
		insert( x, t->right ); // 整体是一个递归
        
	    balance( t ); //第一次真正进入是新的节点。相关节点的高度可能发生变化，要把这种变化改过去
	}

    /**
     * Internal method to insert into a subtree.
     * x is the item to insert.
     * t is the node that roots the subtree.
     * Set the new root of the subtree.
     */
    void insert( Comparable && x, AvlNode * & t )
	{
	    if( t == nullptr )
	    {
		std::cout << "add " << x << std::endl;
		t = new AvlNode{ std::move( x ), nullptr, nullptr };
	    }
	    else if( x < t->element )
	    {
		std::cout << "insertion passing " << t->element << std::endl;
		insert( std::move( x ), t->left );
	    }
	    else if( t->element < x )
	    {
		std::cout << "insertion passing " << t->element << std::endl;
		insert( std::move( x ), t->right );
	    }

	    balance( t );
	}
     
    /**
     * Internal method to remove from a subtree.
     * x is the item to remove.
     * t is the node that roots the subtree.
     * Set the new root of the subtree.
     */
    void remove( const Comparable & x, AvlNode * & t )
	{
	    if( t == nullptr )
		return;   // Item not found; do nothing
        
	    if( x < t->element )
		remove( x, t->left );
	    else if( t->element < x )
		remove( x, t->right );
	    else if( t->left != nullptr && t->right != nullptr ) // Two children
	    {
		t->element = findMin( t->right )->element;
		remove( t->element, t->right );
	    }
	    else
	    {
		AvlNode *oldNode = t;
		t = ( t->left != nullptr ) ? t->left : t->right;
		delete oldNode;
	    }
        
	    balance( t );
	}
    
    static const int ALLOWED_IMBALANCE = 1;  // 静态的不会变
	//const static int ALLOWED_IMBALANCE = 1;  //与上面的相同
	//insert 和最后balance 的路径刚好是来回路，一直更改到root
	//使用递归的写法更加方便（类似于数学的不完全归纳法
	//总工作量依然是theta log(n)+const（因为case1-4更新指针3-6个）
    // Assume t is balanced or within one of being balanced
    void balance( AvlNode * & t )
	{
	    if( t == nullptr )
		return;
	    //std::cout << "balance " << t->element << std::endl;
        
	    if( height( t->left ) - height( t->right ) > ALLOWED_IMBALANCE )  //左比右大
		if( height( t->left->left ) >= height( t->left->right ) )  //左的左大于左的右 case1
		    rotateWithLeftChild( t );
		else
		    doubleWithLeftChild( t ); //左的左小于左的右 case2
	    else
		if( height( t->right ) - height( t->left ) > ALLOWED_IMBALANCE ) // 右比左大
		    if( height( t->right->right ) >= height( t->right->left ) ) // case4
			rotateWithRightChild( t );
		    else //case 3
			doubleWithRightChild( t );

	    //std::cout << "update the height of " << t->element << std::endl;
	    t->height = max( height( t->left ), height( t->right ) ) + 1; //高度更新
	}
    
    /**
     * Internal method to find the smallest item in a subtree t.
     * Return node containing the smallest item.
     */
    AvlNode * findMin( AvlNode *t ) const
	{
	    if( t == nullptr )
		return nullptr;
	    if( t->left == nullptr )
		return t;
	    return findMin( t->left );
	}

    /**
     * Internal method to find the largest item in a subtree t.
     * Return node containing the largest item.
     */
    AvlNode * findMax( AvlNode *t ) const
	{
	    if( t != nullptr )
		while( t->right != nullptr )
		    t = t->right;
	    return t;
	}


    /**
     * Internal method to test if an item is in a subtree.
     * x is item to search for.
     * t is the node that roots the tree.
     */
    bool contains( const Comparable & x, AvlNode *t ) const
	{
	    if( t == nullptr )
		return false;
	    else if( x < t->element )
		return contains( x, t->left );
	    else if( t->element < x )
		return contains( x, t->right );
	    else
		return true;    // Match
	}
/****** NONRECURSIVE VERSION*************************
	bool contains( const Comparable & x, AvlNode *t ) const
	{
        while( t != nullptr )
	if( x < t->element )
	t = t->left;
	else if( t->element < x )
	t = t->right;
	else
	return true;    // Match

        return false;   // No match
	}
*****************************************************/

    /**
     * Internal method to make subtree empty.
     */
    void makeEmpty( AvlNode * & t )
	{
	    if( t != nullptr )
	    {
		makeEmpty( t->left );
		makeEmpty( t->right );
		delete t;
	    }
	    t = nullptr;
	}

    /**
     * Internal method to print a subtree rooted at t in sorted order.
     */
    void printTree( AvlNode *t ) const
	{
	    if( t != nullptr )
	    {
		printTree( t->left );
		cout << t->element << " ";
		printTree( t->right );
	    }
	}

    /**
     * Internal method to clone subtree.
     */
    AvlNode * clone( AvlNode *t ) const
	{
	    if( t == nullptr )
		return nullptr;
	    else
		return new AvlNode{ t->element, clone( t->left ), clone( t->right ), t->height };
	}
    // Avl manipulations
    /**
     * Return the height of node t or -1 if nullptr.
     */
    int height( AvlNode *t ) const
	{
	    return t == nullptr ? -1 : t->height;
	}

    int max( int lhs, int rhs ) const
	{
	    return lhs > rhs ? lhs : rhs;
	}

    /**
     * Rotate binary tree node with left child.
     * For AVL trees, this is a single rotation for case 1.
     * Update heights, then set new root.
	 * 智云课堂10.13 14:30左右
     */
    void rotateWithLeftChild( AvlNode * & k2 )
	{
	    //std::cout << "rotate " << k2->element << std::endl;
	    AvlNode *k1 = k2->left;    
	    k2->left = k1->right; 
	    k1->right = k2;
	    //std::cout << "update the height of " << k2->element << std::endl;
	    k2->height = max( height( k2->left ), height( k2->right ) ) + 1; //调节k2的高度
	    //std::cout << "update the height of " << k1->element << std::endl;
	    k1->height = max( height( k1->left ), k2->height ) + 1; //调节k1的高度
	    k2 = k1; //更改指针引用，同时将另一个节点直接反馈
	}

    /**
     * Rotate binary tree node with right child.
     * For AVL trees, this is a single rotation for case 4.
     * Update heights, then set new root.
     */
    void rotateWithRightChild( AvlNode * & k1 )
	{
	    //std::cout << "rotate " << k1->element << std::endl;

	    AvlNode *k2 = k1->right;
	    k1->right = k2->left;
	    k2->left = k1;
	    //std::cout << "update the height of " << k1->element << std::endl;
	    k1->height = max( height( k1->left ), height( k1->right ) ) + 1;
	    //std::cout << "update the height of " << k2->element << std::endl;
	    k2->height = max( height( k2->right ), k1->height ) + 1;
	    k1 = k2;
	}

    /**
     * Double rotate binary tree node: first left child.
     * with its right child; then node k3 with new left child.
     * For AVL trees, this is a double rotation for case 2.
     * Update heights, then set new root.
     */
    void doubleWithLeftChild( AvlNode * & k3 )
	{
	    rotateWithRightChild( k3->left );
	    rotateWithLeftChild( k3 );
	}

    /**
     * Double rotate binary tree node: first right child.
     * with its left child; then node k1 with new right child.
     * For AVL trees, this is a double rotation for case 3.
     * Update heights, then set new root.
     */
    void doubleWithRightChild( AvlNode * & k1 )
	{
	    rotateWithLeftChild( k1->right );
	    rotateWithRightChild( k1 );
	}

    /**
     * Internal method to print a subtree rooted at t in sorted order.
     */
    void displayTree( AvlNode *t ) const
	{
	    queue<AvlNode*> nodes_tree;
	    if (t == nullptr)
	    {
		std::cout << "Empty tree." << std::endl;
		return;
	    }
		
	    nodes_tree.push(t);
	    while (!nodes_tree.empty())
	    {
		AvlNode* tmp = nodes_tree.front();
		if (tmp != nullptr)
		{
		    std::cout << tmp->element << ", ";
		    nodes_tree.push(tmp->left);
		    nodes_tree.push(tmp->right);
		}
		else
		    std::cout << "-1, ";
		nodes_tree.pop();
	    }
	    std::cout << "\b\b" << std::endl;
	}

	/**
	 * @brief 打印二叉树上某段区间的元素
	 * 
	 * @param t 
	 * @param k1 
	 * @param k2 
	 */
	void printAvl(AvlNode *t, Comparable k1, Comparable k2) const
	{
    	if( t != nullptr )
		{
			if (t->element >= k1)
				printAvl( t->left,k1,k2 );
			if (t->element>=k1 && t->element <=k2)
			{
				cout << t->element << " ";
			}
			if(t->element <=k2)
				printAvl(t->right,k1,k2);
		}
	}

};

#endif
